import java.util.Arrays;

public class OptimalImageCompression {
    /**
     * 请看下面的例子.设输入的灰度值序列是：
     *
     * ​ P =<10,12,15,255,1,2,1,1,2,2,1,1>
     *
     * 分法1 S1= <10，12，15>，S2 =<255>，S3=<1，2，1，1，2，2，1，1>
     *
     * 分法2 S1=<10，12，15，255，1，2，1，1，2，2，1，1>
     *
     * 分法3 S1=<10>，S2=<12>，S3=<15>，S4=<255>，S5=<1>，S6=<2>，S7=<1>，S8=<1>，S9=<2>，S10=<2>，S11=<1>，S12=<1>
     *
     * ​ 分法1有3段，第1段3个像素，每个像素用4位；第2段1个像素，每个像素用8位；第3段8个像素，每个像素用2位；加上3个段头，每个段头11位，总计位数是：
     * 4×3+8×1+2×8+3×11=69
     *
     * ​ 分法2有1段，12个像素，每个像素用8位，段头11位，总计位数是：
     * 8×12+11=107
     *
     * ​ 分法3有12段，前3段的像素用4位，第4段像素用8位，后面有5段像素用1位，3段像素用2位，还有12个段头，每个11位，总计位数是：
     * 4×3+8×1+1×5+2×3+11×12=163
     *
     * 看起来分法1占用的位数最少.我们的问题是寻找存储位数最少的分段方法.
     * ————————————————
     */

    /**
     * 假设dp[i]是表示字符串前i个像素点的保存的最少二进制的数量；从1开始计数，我们最终要求处的是dp[P.length]
     * 即为像素序列P的最少消耗空间；
     * 假设每个分段的数量为j，则题目的约束条件是1<=j<=min(i,256).
     * dp[i] = dp[i - j] + j x log2max(Pi-j+1,…,Pi) + 11;
     *
     * 初始化：dp[0]=0;
     *
     * 计算顺序：从左到右
     */

    /**
     * 最优图像函数位数
     * @author ShakeJ
     * @date 2024/1/1
     */

        public int optimalBits(int[] dots, int[] traces) {
            int[] dp = new int[dots.length + 1];
            int cost = Integer.MAX_VALUE;
            //初始化行
            dp[0] = 0;
            for (int i = 1; i <= dots.length; i++) {
                dp[i] = Integer.MAX_VALUE;
                for (int j = 1; j <= Math.min(i, 256); j++) {
                    cost = dp[i - j] + j * (this.minBits(this.max(dots, i - j + 1, i))) + 11;
                    if (cost < dp[i]) {
                        dp[i] = cost;
                        traces[i] = j;
                    }
                }
            }
            return dp[dots.length];
        }

        public void print(int[] traces, int length) {
            length -= traces[length];
            if (length <= 0) {
                return;
            }
            print(traces, length);
            System.out.print(length + " ");
        }

        private int max(int[] dots, int start, int end) {
            int[] copy = Arrays.copyOfRange(dots, start - 1, end);
            Arrays.sort(copy);
            return copy[copy.length - 1];
        }

        private int minBits(int number) {
            int bits = 0;
            for (int i = 1; i <= 8; i++) {
                if (Math.pow(2, i - 1) - 1 <= number && Math.pow(2, i) - 1 >= number) {
                    bits = i;
                    break;
                }
            }
            return bits;
        }

        public static void main(String[] args) {
            int[] dots = new int[]{10, 12, 15, 255, 1, 2, 1, 1, 2, 2, 1, 1};
            int[] traces = new int[dots.length + 1];
            OptimalImageCompression optimalImageCompression = new OptimalImageCompression();
            System.out.println("最少二进制位：" + optimalImageCompression.optimalBits(dots, traces));
            System.out.print("切分位置：");
            optimalImageCompression.print(traces, dots.length);
        }
}